最近在刷 LeetCode,今天要來跟大家分享一下我解「383. Ransom Note」的過程!這題雖然標示為 Easy,解題邏輯不難,但因為對語法不熟,還是讓我卡了一下,所以想把我的解題過程記錄下來,方便未來複習檢視,也給跟我一樣正在學習的朋友們一個參考。如果大神路過有更好的建議幫助我進步歡迎在下方留言。
簡單來說,就是給你兩個字串,一個是「ransomNote」(贖金信),另一個是「magazine」(雜誌)。題目要我們判斷,ransomNote 裡面的每個字母,能不能從 magazine 裡面找到對應的字母,而且每個字母只能用一次。
一開始,我想到幾個簡單的判斷條件:
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# 檢查字數和字母種類
if len(ransomNote) > len(magazine) or not set(ransomNote).issubset(set(magazine)):
return False
# 建立字母頻率表
magz_table = dict()
for m in magazine:
magz_table[m] = magz_table.get(m, 0) + 1
# 逐一檢查 ransomNote
for r in ransomNote:
if r not in magz_table or magz_table[r] == 0:
return False
else:
magz_table[r] -= 1
return True
時間複雜度:O(n + m)
空間複雜度:O(n + m)
我們可以使用 Python 的 collections.Counter 來取代手動建構 hash table。
註:
另外,可以去掉 subset 檢查部分,因為這與構建 hash table 相比並不提供顯著的優勢,直接在遍歷 ransomNote 時做檢查即可。
from collections import Counter
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# 檢查字數是否足夠
if len(ransomNote) > len(magazine):
return False
# 建立字母頻率表
magz_counter = Counter(magazine)
# 逐一檢查 ransomNote
for char in ransomNote:
if magz_counter[char] == 0:
return False
magz_counter[char] -= 1
return True
時間複雜度:O(n + m)
空間複雜度:O(n)
長度檢查和集合子集檢查:
len(ransomNote) > len(magazine) 需要 O(1) 時間。
set(ransomNote) 和 set(magazine) 的創建時間都是 O(n) 和 O(m),其中 n 是 ransomNote 的長度,m 是 magazine 的長度。
set(ransomNote).issubset(set(magazine)) 的檢查時間是 O(n),因為子集檢查在最壞情況下需要遍歷 ransomNote 中的每個字符。
綜上,這部分的時間複雜度是 O(n + m)。
構建 magz_table:
遍歷 magazine 需要 O(m) 時間,每個字符的插入或更新操作在 hash table 中是 O(1) 時間。
因此,這部分的時間複雜度是 O(m)。
檢查並更新 magz_table:
遍歷 ransomNote 需要 O(n) 時間,每個字符的查找和更新操作在 hash table 中是 O(1) 時間。
因此,這部分的時間複雜度是 O(n)。
綜合來看,總的時間複雜度是 O(n + m)。
set(ransomNote) 和 set(magazine) 各自需要 O(n) 和 O(m) 的空間。
hash table magz_table 最多包含 magazine 中所有不同字符的數量,最壞情況下需要 O(m) 的空間。
如果另外用 counter 創建 ransom_note_count 的 hash table 最壞情況下需要 O(n) 的空間。
綜合來看,總的空間複雜度是 O(n + m)。
在寫程式的時候,我卡在了一個小細節:
print(set(ransomNote)) # Output: {'a'}
print(set(magazine)) # Output: {'a', 'b'}
print(set(ransomNote) not in set(magazine)) # Output: True
我原本以為 set(ransomNote) not in set(magazine)
可以判斷 ransomNote 的字母是不是 magazine 的子集,但
後來我才發現,not in
因為它的意思是檢查 set(ransomNote)
是否作為一個整體元素存在於 set(magazine)
中,而不是判斷一個集合是不是另一個集合的子集。正確的做法應該是使用 issubset()
。
假設 ransomNote
為 "aa"
,magazine
為 "aab"
:
set(ransomNote)
是 {'a'}
。set(magazine)
是 {'a', 'b'}
。使用 issubset
方法:
set(ransomNote).issubset(set(magazine)) # True
使用 not in
方法:
set(ransomNote) not in set(magazine) # True
前者是正確的,因為它檢查 'a'
是否在 {'a', 'b'}
中。而後者是不正確的,因為 {'a'}
不是 {'a', 'b'}
的一個元素。
這題幫我
當需要計算元素出現的次數時,例如字符、單詞、或數字的頻率。
例子:統計字符串中每個字符的出現次數,檢查兩個字符串是否為字母異位詞(Anagram)。
當需要快速查找某個元素是否存在時。
例子:從一個列表中快速查找某個值,或在 dictionary 中查找某個鍵是否存在。
當需要檢查元素是否唯一時。
例子:檢查一個字符串中的字符是否全都唯一,檢查一組數字中是否有重複值。
當需要建立一對一對應或一對多對應的關係時。
例子:將每個單詞映射到其定義,或將學生 ID 映射到學生信息。
當需要累積計算某些數據時,例如求和、計算最大值或最小值。
例子:累積計算不同產品的銷售額,統計每個類別的商品數量。